1. Technical Field
The present invention relates generally to data processing systems and relates specifically to databases. More specifically, the present invention relates to performing disjunctive single-index access on a database in a data processing system.
2. Description of the Related Art
Predicates containing OR conditions present challenges for database management systems in determining the most efficient access to data. One typical approach for improving query performance for such predicates involves exploiting multiple index access as described in “Single Table Access Using Multiple Indexes: Optimization, Execution and Concurrency Control Techniques” by C. Mohan, Don Haderle, Yun Wang, Josephine Cheng. Another alternative involves rewriting the predicates into either conjunctive or disjunctive normal form to best exploit either a single or multiple indexes respectively as described in “Factorizing Complex Predicates in Queries to Exploit Indexes” by Surajit Chaudhuri, Prasanna Ganesan, Sunita Sarawagi.
When the columns referenced are common to each OR predicate, then it may be possible to match these to the same index. For cases where the OR references a single column, such as the structure WHERE C1=? OR C1=? OR C1=?, then database management systems are known to already simplify this to the form WHERE C1 IN (?, ?, ?). Unfortunately, when multiple columns are referenced in the OR, multi-index access may be used and will invoke multiple probes of the same index. The problem with this approach is that ordering is not maintained by the multiple index access steps, and thus a final sort is required if an ORDER BY was specified that could have been satisfied by the index. Since ordering is not maintained, then there is no way to terminate the ORing early if only the first “n” rows are required. This is a common requirement for cursor scrolling applications. An additional limitation of the multi-index access as proposed in the aforementioned article is that index-only access is not supported, even if all required columns are available in the chosen indexes.
Rewriting the predicates into disjunctive normal form promotes exploitation of multi-index access which then introduces the aforementioned limitations, specifically loss of order and inability to terminate early. Rewriting the predicates into conjunctive normal form supports exploitation of single index access which can then support ordering without the requirement for sort. However, the conjunctive predicates may be less selective or may still involve OR'd predicates, and thus full matching of the single index may not be possible.
In addition, many of the existing solutions for improving processing of complex OR predicates involve detailed analysis of overlapping ranges or duplication of filtering which can be consolidated resulting in a reduction of the predicates to be applied. Such processing however requires complex evaluation of such predicates which can add additional overhead to the prepare or runtime processing depending on when the literal values are known.
What is needed is a method, system and computer program product for simplifying the processing of OR'd predicates that can be mapped to a single index.